package com.tgy.algorithm._经典题目01;

/**
 *
 * 给定两个字符串str1和str2，再给定三个整数ic、dc和rc，分别代表插入、删 除和替换一个字符的代价，
 * 返回将str1编辑成str2的最小代价。【
 * 举例】
 * str1="abc"，str2="adc"，
 * ic=5，dc=3，rc=2
 * 从"abc"编辑成"adc”，
 * 把'b'替换成'd'是代价最小的，所以返回2
 * str2="adc"，
 * ic=5，dc=3，[c=100
 * 从"abc"编辑成"adc"，先删除b'，然后str1="abc".插入'd'是代价最小的，所以返回8
 * str1="abc"，
 * str2="abc"，ic=5，dc=3，c=2
 * 不用编辑了，本来就是一样的字符串所以返回0
 */
public class _027_最小编辑距离 {

    public static int minEditorDistance(String one, String two, int ic, int dc, int rc) {

        if (one == null || two == null || one.length() == 0 || two.length() == 0) {
            return 0;
        }

        int oneLen = one.length();
        int twoLen = two.length();
        
        int[][] cache = new int[oneLen + 1][twoLen + 1];

        for (int i = 1; i <= twoLen; i++) {
            cache[0][i] = i * ic; 
        }

        for (int i = 1; i <= oneLen; i++) {
            cache[i][0] = i * dc;
        }
        char[] oneChars = one.toCharArray();
        char[] twoChars = two.toCharArray();

        for (int i = 1; i <= oneLen; i++) {
            char oneChar = oneChars[i - 1];
            for (int j = 1; j <= twoLen; j++) {
                char twoChar = twoChars[j - 1];
                if (oneChar == twoChar) {
                    cache[i][j] = cache[i - 1][j - 1];
                }else {
                    cache[i][j] = cache[i - 1][j - 1] + rc;
                }
                cache[i][j] = Math.min(cache[i][j],cache[i][j - 1] + ic);
                cache[i][j] = Math.min(cache[i][j],cache[i - 1][j] + dc);
            }
        }

        return cache[oneLen][twoLen];
    }

    public static void main(String[] args) {

//        int i = minEditorDistance("abc", "adc", 5, 3, 2);
//        int i = minEditorDistance("abc", "adc", 5, 3, 100);
        int i = minEditorDistance("abc", "abc", 5, 3, 100);
        System.out.println(i);
    }
}
